package linkedlist.pro;

import linkedlist.ListNode;

/**
 * @Classname : SortList
 * @Description :
 * <a href="https://leetcode.cn/problems/sort-list/">148. 排序链表</a>
 * @Author : chentianyu
 * @Date 2022/12/27 23:05
 */


public class SortList {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;

        // 找到中点节点
        ListNode fast = head, slow = head;
        while (fast.next != null && fast.next.next != null) {  // 奇数节点，slow停在中点；偶数节点，slow停在左半段最后一个节点
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode next = slow.next;
        slow.next = null;  // 注意需要将两段链表断开！
        // 递归排序左右两段链表
        ListNode left = sortList(head);
        ListNode right = sortList(next);
        // 合并左右两段已排序的链表
        return mergeSortedList(left, right);
    }

    // 合并两个升序链表
    private ListNode mergeSortedList(ListNode left, ListNode right) {
        ListNode dummy = new ListNode(), tail = dummy;
        while (left != null && right != null) {
            if (left.val < right.val) {
                tail.next = left;
                left = left.next;
            } else {
                tail.next = right;
                right = right.next;
            }
            tail = tail.next;
        }
        tail.next = (left == null ? right : left);
        return dummy.next;
    }
}
